Cache memory is one of the critical elements in computer processors for achieving good performance on the processors. Generally, a cache is a smaller, faster memory used by a central processing unit of a computer to reduce the average time to access its data or instructions. The cache typically stores copies of the data from the most frequently used main memory locations. The fundamental idea of cache organization is that by keeping the most frequently accessed instructions and data in the fast cache memory, the average memory access time will approach the access time of the cache. A cache miss is costly because the data must then be fetched from a higher-level cache, main memory, or potentially another processor's cache on a multiprocessor, which incurs a delay because accessing the other memory is slower than accessing the cache memory. Thus, maximizing the cache's hit rate is one of the important factors in achieving good performance.
When a cache miss occurs, one of the existing entries needs to be replaced to make room for the new entry. Different replacement policies or rules exist for replacing the entries. One common algorithm used by the hardware is Least Recently Used (LRU), which replaces the least recently used entry, for instance. While LRU performs well in many cases, it may not be suitable for some situations. A streaming application is an example application where LRU cache replacement may not have the desired performance.
In addition, existing cache solutions typically apply a fixed algorithm across all applications and do not consider requirements that change from application to application or those applications that have requirements that change over time. A known technique allows a given line to be pinned in the cache, however, pinning does not capture the temporal nature of many cache lines. Another known method allows a user to specify the importance of certain cache lines, but there is no temporality associated with the indication. Other existing work looks at distinguishing between temporal and non-temporal data, however, does not consider varying indication values of cache lines over time.
Various requirements that change over time sometimes can be deduced in hardware from the memory access patterns. Also, software or the operating system can determine different access patterns among different applications or threads. In other cases the operating system can proactively know the behavior of a given application. What is needed is a cache replacement mechanism that allows the dynamic characteristics of reference patterns to be taken into consideration. Hardware alone may take advantage of this mechanism and improve performance for some applications. Additional benefit can be gained because software, such as a hypervisor or other, or the operating system can also determine the expected access pattern, or can proactively know the expected access patterns; what is needed is a mechanism that allows software to affect the cache replacement algorithm.